package me.qingy.programmatic;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.HashMap;

/**
 * 两层 for 循环，或 Map，或 排序+双指针
 *
 * @author qingy
 * @since 2021/8/18
 */
public class TwoSum {
    /**
     * 暴力穷举法
     * 时间复杂度 O(n^2) 空间复杂度 O(1)
     * 时间复杂度依赖于输入，最理想情况甚至可达到O(1)，但现实往往不是如此
     */
    public int[] twoSum1(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("no solution");
    }

    /**
     * Map 登记法 空间换时间
     * 时间复杂度 O(n) 空间复杂度 O(n)
     */
    public int[] twoSum2(int[] nums, int target) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>(n);

        for (int i = 0; i < n; i++) {
            // put 时间复杂度(1)
            map.put(nums[i], i);
        }

        for (int i = 0; i < n; i++) {
            int tharNum = target - nums[i];
            // containsKey 与 get是哈希表通过哈希值匹配值，并不会涉及到遍历，所以这儿的时间复杂度是O(1)
            if (map.containsKey(tharNum) && i != map.get(tharNum)) {
                return new int[]{i, map.get(tharNum)};
            }
        }

        throw new IllegalArgumentException();
    }

    public int[] twoSum3(int[] nums, int target) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>(nums.length);

        for (int i = 0; i < n; i++) {
            int thatNum = target - nums[i];
            if (map.containsKey(thatNum) && i != map.get(thatNum))
                // 与上边解法输出的数组内值顺序一致
                return new int[]{map.get(thatNum), i};

            // 相当于从后往前找
            map.put(nums[i], i);
        }

        throw new IllegalArgumentException("no solution");
    }

    @Test
    public void testTwoSum() {
        Assertions.assertArrayEquals(new int[]{0, 1}, twoSum1(new int[]{2, 7, 11, 15}, 9));
        Assertions.assertArrayEquals(new int[]{1, 2}, twoSum1(new int[]{3, 2, 4}, 6));
        Assertions.assertArrayEquals(new int[]{0, 1}, twoSum1(new int[]{3, 3}, 6));
        Assertions.assertArrayEquals(new int[]{0, 2}, twoSum1(new int[]{3, 2, 3}, 6));
    }

}
